package org.hot100_1;

import org.algorithm.List.ListNode;

public class leetcode33 {
    public ListNode sortList(ListNode head) {

        return split(head,null);
    }

    //left =[head,mid),right = [mid,tail)
    private ListNode split(ListNode head,ListNode tail){

        if (head==null){
            return head;
        }

        if (head.next==tail){
            head.next=null;
            return head;
        }

        ListNode fast = head;
        ListNode slow = head;

        while (fast!=tail){
            fast=fast.next;
            slow=slow.next;

            if (fast!=tail){
                fast=fast.next;
            }
        }

        ListNode mid = slow;

        ListNode left = split(head, mid);
        ListNode right = split(mid,tail);

        return merge(left,right);
    }

    private ListNode merge(ListNode left,ListNode right){
        ListNode dummy = new ListNode(-1);
        ListNode sortList = dummy;

        while (left!=null && right!=null){
            if (left.val<right.val){
                sortList.next=left;
                left=left.next;
            }else {
                sortList.next=right;
                right=right.next;
            }
            sortList=sortList.next;
        }

        if (left==null){
            sortList.next=right;
        }
        if (right==null){
            sortList.next=left;
        }

        return dummy.next;
    }
}
